package version1;

/** 求next数组
 * @author zhangjiayuan@qipeipu.com
 * @date 2019/1/6 11:47
 * @since 1.0.0
 */
public class Kmp {
    public static int[] getNext(String ps) {
        char[] p = ps.toCharArray();       //p是要进行匹配的字符串
        int[] next = new int[p.length];     //next数组
        next[0] = -1;           //第0个初始化为-1
        int j = 0;
        int k = -1;     // j指针将要移动到的位置
        while (j < p.length -1) {      //当j指针小于p长度减1时(?)
            if (k == -1 || p[j] == p[k]) {    //abababca                       //初始化或是值匹配成功时
                System.out.println(j+"=="+k);   //重点
                next[++j] = ++k;    //第1个初始化为0
            } else {
                k = next[k];
            }
        }
        return next;
    }

    public static void main(String[] args) {
        String ps = "abababca";
        int[] results = Kmp.getNext(ps);
        for (int result : results) {
            System.out.print(result+" ");
        }
    }
}
